package me.out1kiss.www;

import java.util.*;

/**
 * K-means 聚类算法：
 * 将一群随机分布的点，分成Ｋ个集群，Ｋ是我们自己指定的．
 * １,开始在所有点里随机选择Ｋ个点作为质心（可以理解为暂定的中心点），根据欧式距离公式（sqrt((x1-x2)^2+(y1-y2)^2)）计算出各个点到质心的距离，距离越小，相似度越高．
 * ２,然后在分开的Ｋ个集群内，重新计算质心（x=(x1+x2+...+xn)/n,y=(y1+y2+...+yn)/n）.
 * 得到质心后，重新根据欧式距离重新分类，重复１，２两步．
 * 关于结束：
 * １,设定一个ｍ值，只会做ｍ次的聚类，也就是循环ｍ次．
 * ２,设定一个ｔ值，当前质心比较移动距离小于ｔ值，则认认为结束循环．
 */
public class KMeans {

    private List<Point> data;
    private Integer loopCount;
    private Double limitCentroidMoveDistance;
    private Integer groupNum;
    private Map<Point, Set<Point>> centroid;

    private KMeans() {
    }

    /**
     *
     * @param data 数据集合
     * @param loopCount　循环次数，聚类次数大于该值，算法结束
     * @param limitCentroidMoveDistance　最小移动距离，小于该值时，算法结束
     * @param groupNum　分组数量
     * @return 实体
     */
    public static KMeans initialize(List<Point> data, Integer loopCount, Double limitCentroidMoveDistance, Integer groupNum) {
        KMeans kMeans = new KMeans();
        kMeans.data = data;
        kMeans.loopCount = loopCount;
        kMeans.limitCentroidMoveDistance = limitCentroidMoveDistance;
        kMeans.groupNum = groupNum;
        kMeans.centroid = kMeans.initializeCentroid();//初始化中心点，在范围内取随机集合内的多个点
        return kMeans;
    }

    private Map<Point, Set<Point>> initializeCentroid() {
        assert this.data != null && this.data.size() > 0 && groupNum != null && groupNum > 0;
        Set<Integer> centroidIndexes = new HashSet<>();
        Map<Point, Set<Point>> centroid = new HashMap<>();
        while (centroidIndexes.size() < groupNum) {
            centroidIndexes.add((int) (Math.random() * data.size()));
        }
        for (Integer centroidIndex : centroidIndexes) {
            centroid.put(data.get(centroidIndex), new LinkedHashSet<>());
        }
        return centroid;
    }

    /**
     * 重新计算中心点
     * @return 中心点的最大移动距离
     */
    private double resetCentroid() {
        double maxCentroidMoveDistance = 0.00;
        Map<Point, Set<Point>> newCentroid = new HashMap<>();
        for (Map.Entry<Point, Set<Point>> entry : centroid.entrySet()) {
            Point newPoint = new Point();
            newPoint.x = 0.00;
            newPoint.y = 0.00;
            for (Point point : entry.getValue()) {
                newPoint.x += point.getX();
                newPoint.y += point.getY();
            }
            newPoint.setX(newPoint.getX() / (double) entry.getValue().size());
            newPoint.setY(newPoint.getY() / (double) entry.getValue().size());
            newCentroid.put(newPoint, entry.getValue());
            double centroidMoveDistance = calculate(entry.getKey(), newPoint);
            if (maxCentroidMoveDistance < centroidMoveDistance) {
                maxCentroidMoveDistance = centroidMoveDistance;
            }
        }
        centroid = newCentroid;
        return maxCentroidMoveDistance;
    }

    //运行代码
    public void run() {
        assert this.loopCount != null || this.limitCentroidMoveDistance != null;
        int count = 0;
        while (true) {
            categorization();
            double centroidMoveDistance = resetCentroid();
            if (limitCentroidMoveDistance != null && centroidMoveDistance < limitCentroidMoveDistance) {
                return;
            }
            if (loopCount != null && count++ >= loopCount) {
                return;
            }
            System.out.println(count++ + "次:" + centroid);
        }
    }

    private void categorization() {
        if (centroid == null) {
            centroid = initializeCentroid();
        }
        for (Point point : data) {
            Point minDistancePoint = new Point();
            double minDistance = Double.MAX_VALUE;
            for (Point centroidPoint : centroid.keySet()) {
                double distance = calculate(centroidPoint, point);
                if (minDistance > distance) {
                    minDistance = distance;
                    minDistancePoint = centroidPoint;
                }
            }
            for (Map.Entry<Point, Set<Point>> entry : centroid.entrySet()) {
                if (minDistancePoint.x.equals(entry.getKey().x) && minDistancePoint.y.equals(entry.getKey().y)) {
                    entry.getValue().add(point);
                }
            }
        }
    }

    private double calculate(Point centroidPoint, Point point) {
        return Math.sqrt((centroidPoint.x - point.x) * (centroidPoint.x - point.x)
                + (centroidPoint.y - point.y) * (centroidPoint.y - point.y));
    }

    public List<Point> getData() {
        return data;
    }

    public void setData(List<Point> data) {
        this.data = data;
    }

    public Integer getLoopCount() {
        return loopCount;
    }

    public void setLoopCount(Integer loopCount) {
        this.loopCount = loopCount;
    }

    public Double getLimitCentroidMoveDistance() {
        return limitCentroidMoveDistance;
    }

    public void setLimitCentroidMoveDistance(Double limitCentroidMoveDistance) {
        this.limitCentroidMoveDistance = limitCentroidMoveDistance;
    }

    public Integer getGroupNum() {
        return groupNum;
    }

    public void setGroupNum(Integer groupNum) {
        this.groupNum = groupNum;
    }

    public Map<Point, Set<Point>> getCentroid() {
        return centroid;
    }

    public void setCentroid(Map<Point, Set<Point>> centroid) {
        this.centroid = centroid;
    }

    public static void main(String[] args) {
        List<Point> data = new ArrayList<>();
        data.add(new Point(1,20));
        data.add(new Point(2,30));
        data.add(new Point(4,60));
        data.add(new Point(7,30));
        data.add(new Point(9,70));
        KMeans kMeans = KMeans.initialize(data, 0, null, 2);
        kMeans.run();
    }
}

class Point {
    Double x;
    Double y;

    public Point() {
    }

    public Point(Double x, Double y) {
        this.x = x;
        this.y = y;
    }

    public Point(int x, int y) {
        this.x = (double) x;
        this.y = (double) y;
    }

    public Double getX() {
        return x;
    }

    public void setX(Double x) {
        this.x = x;
    }

    public Double getY() {
        return y;
    }

    public void setY(Double y) {
        this.y = y;
    }

    @Override
    public String toString() {
        return String.format("[%.2f, %.2f]", x, y);
    }

    @Override
    public int hashCode() {
        return x.hashCode() + y.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Point && this.x.equals(((Point) obj).x) && this.y.equals(((Point) obj).y);
    }
}
